In communication systems it is desirable to minimize the signal-to-noise ratio (SNR), and hence minimize the required transmission power and associated costs, while achieving a specific error rate in the received data after transmission over a noisy communication channel. As well, given a fixed available transmission power, and hence given a fixed SNR, it is desirable to minimize the error rate in the received data. Claude Shannon showed that if a certain minimum SNR limit is exceeded in a communication system, then there exists a coding scheme that ensures error-free communication (C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, pp. 379-423 (Part 1) and pp. 623-656 (Part 2), July, 1948). Numerous coding schemes have been devised in attempts to approach the theoretical coding performance limit demonstrated by Shannon (see Shu Lin and Daniel Costello Jr., “Error Control Coding, 2nd ed., Prentice Hall, 2004 for a review of the relevant literature). Most conventional communication receivers quantize the received signals into bits or vectors of bits, and then optionally use error control schemes that attempt to detect and correct errors in the received bits. Conventional error control schemes employ algorithms that attempt to identify and correct errors in received bits in a single iteration of computation. Gallager's low density parity check (LDPC) codes (R. G. Gallager, “Low Density Parity Check Codes,” IRE Transactions on Information Theory, vol. IT-8, pp. 21-28, January, 1962) have been shown to have error correcting performance that approaches Shannon's limit (see Lin and Costello for a summary of recent results); however, the associated multiple-iteration LDPC decoding algorithm at the receiver is computationally demanding and requires considerable hardware resources, decoding time and energy. These implementation challenges in the iterative decoder have hindered the adoption of LDPC codes. The silicon chip area required by prior art, for example the design described by Blanksby and Howland in “A 690-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder” (IEEE Journal of Solid-State Circuits, vol. 37, no. 3, March 2002, pp. 404-412), is relatively large due in part to the large amount of wiring required by the bit-parallel representation of intermediate binary results. The increasing commercial importance of portable battery-powered communication devices makes it important to seek decoders that minimize the required power consumption, possibly changing the decoding algorithm adaptively in response to changing environmental conditions.
Referring now to FIG. 1, shown is a bipartite probability dependency graph for a block-parallel decoder. The bipartite probability dependency graph contains variable nodes, check nodes, and edges between variable nodes and check nodes that indicate the connection paths taken by variable messages and check messages. The bipartite probability dependency graph for a code of length L will have a set of L variable nodes and a set of T check nodes. Connections exist between the variable nodes and check nodes as defined by a connection matrix, for example a parity check matrix (H) with dimensions T by L. In operation, processing occurs in both the variable nodes and the check nodes in accordance with a BPA (Belief Propagation Algorithm), which is an iterative decoding algorithm for use in detecting and correcting errors in data. The corrected bits recovered by the decoding algorithm are output by the variable nodes after the last iteration.